\documentclass[E:/GsjzTle/main/main.tex]{subfiles}
\begin{document}
稠密图稳定$O(n^2)$。


\begin{lstlisting}
int n ;
bool vis[maxn] ;
int dis[maxn][maxn] ;
int lowcost[maxn] ;
int prim()
{
	int sum = 0 ;
	for(int i = 1 ; i <= n ; i ++)  lowcost[i] = 1e9 ;
	memset(vis , 0 , sizeof(vis)) ;
	lowcost[1] = 0 ;
	for(int i = 1 ; i <= n ; i ++)
	{    
		int min1 = 1e9 ;
		int temp = 0 ;
		for(int j = 1 ; j <= n ; j ++)
		if(!vis[j] && lowcost[j] < min1)  min1 = lowcost[j] , temp = j ;
		vis[temp] = 1 ;
		sum += lowcost[temp] ;
		for(int j = 1 ; j <= n ; j ++)
		if(j != temp)
		lowcost[j] = min(lowcost[j] , dis[temp][j]) ; 
	}
	return sum ;
}
\end{lstlisting}
\end{document}


